package java0406;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    // 两数之和 II - 输入有序数组
    // 给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
    //
    //函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
    //
    //你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int[] ret = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            map.put(numbers[i], i);
        }
        for (int i = 0; i < numbers.length; i++) {
            if (map.get(target - numbers[i]) != null) {
                ret[0] = i + 1;
                ret[1] = map.get(target - numbers[i]) + 1;
                return ret;
            }
        }
        return null;
    }

    // 移除元素
    // 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
    //
    //不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
    //
    //元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
    public int removeElement(int[] nums, int val) {
        int index1 = 0;
        int index2 = 0;
        int ret = 0;
        while (index2 < nums.length
                && index1 < nums.length) {
            while (index1 < nums.length && nums[index1] != val) {
                index1++;
            }
            index2 = index1 + 1;
            while (index2 < nums.length && nums[index2] == val) {
                index2++;
            }
            if (index2 >= nums.length) {
                break;
            }
            int tmp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = tmp;
            ret++;
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] a = {0,1,2,2,3,0,4,2};
        Solution solution = new Solution();
        solution.removeElement(a, 2);
        System.out.println(Arrays.toString(a));
    }
}
